'''
    题目：
        给定一个整数数组 nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

        示例 1：

        输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
        输出：6
        解释：连续子数组[4,-1,2,1] 的和最大，为6 。

    思路：
        本题采用动态规划的方法，
        假设f(i)表示当前序列第i个索引的最大和，
        那么状态转移方程为f(i) = max(f(i - 1) + num,f(i - 1)),主要是用来判断当前数字对于和的增加是否有用（num是正数就有用，否则没用），
        此时需要比较f(i)的值和之前的最大值ans，如果f(i)比较大，就更新目前为止的最大值是f(i)，否则还是保留之前计算出的最大值ans.

    时间复杂度：O(n)
    空间复杂度：O(1)
'''

class Solution:
   def maxSubArray(self,nums:List[int])->int:
       pre = 0
       ans = nums[0]
       for num in nums:
           pre = max(pre+num,num)
           ans = max(ans,pre)
       return ans